/*================================================================
*   文件名称：main.cpp
*   创 建 者：yang qiang
*   创建日期：2018年07月17日
*   描    述：
*   
================================================================*/


#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    /**
     * @param nums: An integer array
     * @return: The length of LIS (longest increasing subsequence)
     */
    int longestIncreasingSubsequence(vector<int> &nums) {
        // write your code here
        int len = nums.size();
        if( len == 0 )
            return 0;
        
        int dp[len];
        int maxlen = 1;;
        for(int i = 0; i < len; i++)
            dp[i] = 1;
        for(int j = 1; j < len; j++){
            for( int k = 0; k < j; k++){
                if( nums[j] > nums[k] )
                    dp[j] = max(dp[j], dp[k] + 1);
            } 
            maxlen = max(dp[j], maxlen);
        }

        return maxlen;
	}
};

class Solution {
public:
    /**
     * @param nums: The integer array
     * @return: The length of LIS (longest increasing subsequence)
     */
    int longestIncreasingSubsequence(vector<int> nums) {
        // write your code here
        int size = nums.size(), i = 0;
        vector<int> stack;

        if(size <= 0) {
            return 0;
        }

        stack.push_back(nums[0]);
        for(i=1; i<size; i++) {
            if(stack[stack.size()-1] < nums[i]) {
                stack.push_back(nums[i]);
            }
            else {
                int low = 0, high = stack.size()-1, mid = 0;
                while(low <= high) {
                    mid = low + (high - low) / 2;
                    if(nums[i] > stack[mid]) {
                        low = mid + 1;
                    }
                    else {
                        high = mid - 1;
                    }
                }
                stack[low] = nums[i];
            }
        }
        return stack.size();
    }
};
